#include "AVLTree.h"
#include <stdlib.h>

inline int GetHeight(AVLNode* node)
{
    return node == NULL ? -1 : node->height;
}

inline int MaxHeight(AVLNode* a, AVLNode* b)
{
    int a_Height = GetHeight(a), b_Height = GetHeight(b);
    return a_Height > b_Height ? a_Height : b_Height;
}

AVLNode* FindMinNode(AVLNode* tree)
{
    AVLNode *tp = tree;
    while (tp->left != NULL)
    {
        tp = tp->left;
    }
    return tp;
}

#pragma region 四种旋转操作
//针对RR型，进行左旋
AVLNode* S_LeftRotate(AVLNode* errNode)
{
    AVLNode *newNode = errNode->right;
    errNode->right = newNode->left;
    newNode->left = errNode;

    errNode->height = MaxHeight(errNode->left, errNode->right) + 1;
    newNode->height = MaxHeight(newNode->left, newNode->right) + 1;
    return newNode;
}

//针对LL型，进行右旋
AVLNode* S_RightRotate(AVLNode* errNode)
{
    AVLNode *newNode = errNode->left;
    errNode->left = newNode->right;
    newNode->right = errNode;

    errNode->height = MaxHeight(errNode->left, errNode->right) + 1;
    newNode->height = MaxHeight(newNode->left, newNode->right) + 1;
    return newNode;
}

//针对RL型，进行左-右双旋转
AVLNode* D_R_Rotate(AVLNode* errNode)
{
    errNode->right = S_LeftRotate(errNode);
    return S_RightRotate(errNode);
}

//针对LR型，进行右-左双旋转
AVLNode* D_L_Rotate(AVLNode* errNode)
{
    errNode->left = S_RightRotate(errNode);
    return S_LeftRotate(errNode);
}
#pragma endregion


AVLNode* Init_AVLNode(int value)
{
    AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 0;
    newNode->value = value;
    return newNode;
}

AVLNode *Insert_AVLNode(AVLNode *tree, int value)
{
    if(tree == NULL)
    {
        tree = Init_AVLNode(value);
    }
    else if(value < tree->value)
    {
        tree->left = Insert_AVLNode(tree->left, value);
        //判断是否失衡
        if(GetHeight(tree->left) - GetHeight(tree->right) > 1)
        {
            //若失衡且新节点位于左树，则LL型，需右旋
            if(value < tree->left->value)
                tree = S_RightRotate(tree);
            else //否则位于右树，LR型
                tree = D_R_Rotate(tree);
        }
    }
    else if(value > tree->value) //与左时相同
    {
        tree->right = Insert_AVLNode(tree->right, value);
        if(GetHeight(tree->right) - GetHeight(tree->left) > 1)
        {
            if(value > tree->right->value)
                tree = S_LeftRotate(tree);
            else
                tree = D_L_Rotate(tree);
        }
    }
    tree->height = MaxHeight(tree->left, tree->right) + 1;
    return tree;
}

AVLNode *Del_AVLNode(AVLNode *tree, int value)
{
    if(tree == NULL)
        return tree;
    if(value < tree->value)
        tree->left = Del_AVLNode(tree->left, value);
    else if(value > tree->value)
        tree->right = Del_AVLNode(tree->right, value);
    else //找到了，当前tree即为待删除节点
    {
        AVLNode *tp = NULL;
        if(tree->left != NULL && tree->right != NULL)
        {
            //用右树的最小或左数的最大替换被删节点
            tp = FindMinNode(tree->right);
            tree->value = tp->value;
            //将被换的节点删去
            tree->right = Del_AVLNode(tree->right, tree->value);
        }
        else //被换的节点回来到这个分支
        {
            tp = tree;
            tree = tree->left != NULL ? tree->left : tree->right; //保留可能的唯一孩子替换
            free(tp);
        }
    }
    //检查高度
    if(tree != NULL)
    {
        if (GetHeight(tree->left) - GetHeight(tree->right) > 1)
		{
			if (GetHeight(tree->left->left) > GetHeight(tree->left->right))
				tree = S_RightRotate(tree);
			else
				tree = D_R_Rotate(tree);
		}
		else if (GetHeight(tree->right) - GetHeight(tree->left) > 1)
		{
			if (GetHeight(tree->right->right) > GetHeight(tree->right->left))
				tree = S_LeftRotate(tree);
			else
				tree = D_L_Rotate(tree);
		}
		tree->height = MaxHeight(tree->left, tree->right) + 1;  
    }
    return tree;
}